#include <iostream>

using namespace std;

// kmp
int kmp(string S, string T, int next[]){
    int i=1, j=1;
    while(i<=S.length() && j<=T.length()){
        if(j==0 || S[i-1]==T[j-1]){
            i++;
            j++;
        }else{
            j=next[j-1];
        }
    }
    if(j>T.length()){
        return i-j;
    }else{
        return -1;
    }
}

// getNext
void getNext(string T, int next[]){
    int j=0, k=-1;
    next[0]=-1;
    while(j<T.length()-1){
        if(k==-1 || T[j]==T[k]){
            j++;
            k++;
            next[j]=k;
        }else{
            k=next[k];
        }
    }
}

// nextval优化
void getNextval(string T, int nextval[]){
    int j=0, k=-1;
    nextval[0]=-1;
    while(j<T.length()-1){
        if(k==-1 || T[j]==T[k]){
            j++;
            k++;
            if(T[j]==T[k]){
                nextval[j]=nextval[k];
            }else{
                nextval[j]=k;
            }
        }else{
            k=nextval[k];
        }
    }
}

// 遍历数组元素
void printArray(int arr[], int length){
    for(int i=0; i<length; i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

// 以0为最低设定的话,打印数组
void printArray0(int arr[], int length){
    for(int i=0; i<length; i++){
        cout<<arr[i]+1<<" ";
    }
    cout<<endl;
}


int main(){
    string S, T;
    S = "abacaba";
    T = "ababaaababaa";
    int next[T.length()];
    int nextval[T.length()];
    getNext(T, next);
    cout<<"next数组："<<endl;
    printArray(next, T.length());
    printArray0(next, T.length());
    getNextval(T, nextval);
    cout<<"nextval数组："<<endl;
    printArray(nextval, T.length());
    printArray0(nextval, T.length());
    cout<<kmp(S, T, next)<<endl;
    return 0;
}